package com.tgy.递归;

/***
 * @ClassName: Queen
 * @Description: 八皇后问题
 * @Auther: tanggy3
 * @Date: 18:26 2022/8/3
 * @version : V1.0
 */
public class Queen {
    int max = 8;//定义八皇后
    int[] array = new int[max];//存放皇后位置的数组
    static int count = 0;
    static int judgeCount = 0;
    public static void main(String[] args) {
        //不能使用此种方法转换long
        System.out.println(Long.getLong("333L"));
        //测试一把 ， 8皇后是否正确
        Queen queen = new Queen();
        queen.check(0);
        System.out.printf("一共有%d解法", count);
        System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w

    }
    //编写一个方法，放置第n个皇后
    //特别注意： check 是 每一次递归时，进入到check中都有  for(int i = 0; i < max; i++)，因此会有回溯
    private void check(int n) {
        if(n == max){
            print();
            return;
        }
        //这个for循环是一次性输出所有种类的关键
        //当第一个皇后放在第一行得的第一列的所有可能算出来后，for循环继续，把第一个皇后放在第一行的第二列继续运算
        for (int i = 0; i < max; i++) {
            //先把当前这个皇后 n，放到改行的第一列
            array[n]= i;
            //判断当放置第n个皇后到第i列时，是否冲突
            if(judge(n)){//如果不冲突
                //接着放第n个皇后，即开始递归
                check(n+1);
            }//如果冲突  继续执行 array[n] = i;这时候i已经加一了 即将第n个皇后，放置在本行得 后移的一个位置，也就是列移动，向后移动
        }
    }

    /**
     * 判断皇后的位置是否与前面的皇后位置冲突
     * @param n 表示第n+1个皇后,因为从0开始
     * @return
     */
    private boolean judge(int n){
        judgeCount++;
        for (int i = 0; i < n; i++) {//判断与前面的皇后是否冲突！！！
            //同一列或者同一斜率 不行，同一行已经被一维数组排除了
            if(array[i] == array[n] || Math.abs(array[i]-array[n]) == Math.abs(n-i)){
                return false;
            }
        }
        return true;
    }
    //写一个方法，可以将皇后摆放的位置输出
    private void print() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println("=================");
    }
}
